package 暴力递归;

import java.util.ArrayList;
import java.util.List;

public class PrintAllPermutations_distinct {

    public static List<String> permutation(String s){
        List<String> ans = new ArrayList<>();
        if (s == null || s.length() == 0){
            return ans;
        }
        char[] str = s.toCharArray();
        g(str,0,ans);
        return ans;
    }


    public static void g(char[] str,int index, List<String> ans){
        if (index == str.length){
            ans.add(String.valueOf(str));
        }else {
            // index ->
            boolean[] visited = new boolean[256];
            for (int i = index; i < str.length; i++) {
                if (!visited[str[i]]){
                    visited[str[i]] = true;
                    swap(str,index,i);
                    g(str,index+1,ans);
                    swap(str,index,i);
                }
            }
        }
    }

    private static void swap(char[] ch, int i, int j) {
        char tmp = ch[i];
        ch[i] = ch[j];
        ch[j] = tmp;
    }
}
